'''
https://leetcode.cn/problems/minimum-domino-rotations-for-equal-row
'''

from typing import List


class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
        n = len(tops)
        def check(x):
            a_rotated = b_rotated = 0
            for i in range(n):
                if tops[i] != x and bottoms[i] != x:
                    return -1
                elif tops[i] != x:
                    a_rotated += 1
                elif bottoms[i] != x:
                    b_rotated += 1
            return min(a_rotated, b_rotated)
        
        # 由于必须要将所有的位置都反转为一样的
        #   所以可以从任意位置开始
        res1, res2 = check(tops[0]), check(bottoms[0])
        if res1 >= 0 and res2 >= 0:
            return min(res1, res2)
        return max(res1, res2)